//23 Merge k Sorted Lists
/*
给定 k 个增序的链表，试将它们合并成一条增序链表

输入输出样例
	输入是一个一维数组，每个位置存储链表的头节点；输出是一条链表

Input:
[1->4->5,
1->3->4,
2->6]
Output: 1->1->2->3->4->4->5->6
*/
struct Comp
{
	bool operator()(ListNode *l1, ListNode *l2)
	{
		return l1->val > l2->val;
	}
};


ListNode *mergeKLists(vector<ListNode *> &lists)
{
	if (lists.empty())
		return nullptr;

	//
	priority_queue<ListNode *, vector<ListNode *>, Comp> q;
	for (ListNode *list : lists)
	{
		if (list)
		{
			q.push(list);
		}
	}
	ListNode *dummy = new ListNode(0), *cur = dummy;

	//
	while (!q.empty())
	{
		cur->next = q.top();
		q.pop();
		cur = cur->next;
		if (cur->next)
		{
			q.push(cur->next);
		}
	}
	return dummy->next;
}
